šŸ“Š Longest Increasing Subsequence (LIS)

Find the length of the longest strictly increasing subsequence in an array

šŸ‘©ā€šŸ’» Exploring Strictly Increasing Sequences

šŸŽÆ The Mission:

Determine the length of the longest strictly increasing subsequence in an array to identify sorted patterns.

šŸ“‹ Requirements:

  • Compute the length of the longest strictly increasing subsequence
  • Handle arrays of length 1 to 337
  • Elements range from 1 to 10^5
  • Output: "Length of the longest increasing subsequence: "

Input/Output Specifications

  • Input: Integer N (array length), followed by N space-separated integers
  • Output: "Length of the longest increasing subsequence: "

Example: nums = [5, 4, 11, 1, 16, 8]

Array:

5
4
11
1
8
16

LIS Length: 3 (e.g., [1, 8, 16])

Example: nums = [1, 2, 2]

1
2
2

LIS Length: 2 (e.g., [1, 2])

āš” LIS Explained

How LIS Works

  1. Dynamic Programming: Use a DP array where dp[i] is the length of the LIS ending at index i
  2. Compare Elements: For each element, check previous elements where arr[j] < arr[i]
  3. Track Maximum: Keep track of the maximum LIS length

DP Table Example (nums = [5, 4, 11, 1, 16, 8])

Index012345
Element54111168
DP Value112132

LIS Length: 3 (e.g., [1, 8, 16])

Time Complexity

O(NĀ²)

For nested loops over N elements

Space Complexity

O(N)

For DP array

Why LIS?

  • āœ… Identifies longest increasing patterns
  • āœ… Useful in scheduling, bioinformatics
  • āœ… Simple DP approach
  • āŒ Quadratic time for large inputs

šŸ” Step-by-Step LIS Demo

Click "Start Demo" to begin step by step visualization

Algorithm Progress:

1. Display input array
2. Build DP table
3. Display result

Current Array:

DP Table:

šŸŽ® Practice LIS

Enter array and click "Find LIS"

Test Cases

Example 1: nums = [5, 4, 11, 1, 16, 8] ā†’ Length of the longest increasing subsequence: 3

Example 2: nums = [1, 2, 2] ā†’ Length of the longest increasing subsequence: 2

šŸ“Š Algorithm Analysis

LIS Process

  1. Initialize DP: Set dp[i] = 1 for all indices
  2. Compute DP: For each index i, check previous indices j where arr[j] < arr[i]
  3. Update Maximum: Track the maximum dp[i] as the LIS length

Time Complexity

O(NĀ²)

For nested loops over N elements

Space Complexity

O(N)

For DP array

Key Points

  • Dynamic Programming: Efficiently computes LIS length
  • Strictly Increasing: Ensures arr[i] > arr[j]
  • Applications: Sequence analysis, scheduling
  • Limitation: Quadratic time for large inputs